/**
* @description: 周赛314 t4
* @author hewei
* @date 2022/10/9 11:31
* @version 1.0
*/

public class NumberOfPaths {

    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[][][] dp = new int[m + 1][n + 1][k];
        int mod = (int) (1e9 + 7);
        dp[0][1][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l < k; l++) {
                    int temp = ((l - grid[i][j] % k) + k) % k;
                    dp[i + 1][j + 1][l] = (dp[i + 1][j + 1][l] + dp[i][j + 1][temp]) % mod;
                    dp[i + 1][j + 1][l] = (dp[i + 1][j + 1][l] + dp[i + 1][j][temp]) % mod;
                }
            }
        }
        return dp[m][n][0];
    }
}